/*
 * Copyright (C) 2010-2011 Graz University of Technology, Austria. All Rights reserved. 
 *
 * Contact: Simone Kopeinik <simone.kopeinik@tugraz.at>
 * 	   Graz University of Technology, Knowledge Management Institute, Brückenkopfgasse 1/6, 8020 Graz 	
 * 	   <http://www.kmi.tugraz.at/>
 * 
 * This software is part of the TARGET platform developed by the
 * TARGET EC-funded project www.reachyourtarget.org
 *
 * This software is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, version 3.
 *
 * This software is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * The GNU General Public License is available at <http://www.gnu.org/licenses/>.
 *
 */
package at.tugraz.kmi.css.cbkst2.prereq;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.logging.Level;
import java.util.logging.Logger;

import at.tugraz.kmi.css.cbkst2.CbKSTVertex;
import at.tugraz.kmi.css.cbkst2.ImmutablePrerequesiteOrderSet;
import at.tugraz.kmi.css.cbkst2.PrerequesiteOrderSet;
import at.tugraz.kmi.css.cbkst2.PrerequesiteRelation;

import com.google.common.collect.ImmutableSet;
import com.google.inject.Inject;

import edu.uci.ics.jung.graph.DirectedSparseGraph;
import edu.uci.ics.jung.graph.ObservableGraph;
import edu.uci.ics.jung.graph.event.GraphEventListener;
import edu.uci.ics.jung.graph.util.EdgeType;
import edu.uci.ics.jung.graph.util.Pair;

/**
 * Graph based datastructure that implements a {@link PrerequesiteOrderSet}.
 * Only injectable and not instantiable ...
 * 
 * @author Georg Öttl <georg.oettl@gmail.com>
 * 
 * @param <V>
 * @param <E>
 */
class JungPrerequesiteGraph<V extends CbKSTVertex, E extends PrerequesiteRelation>
		extends DirectedSparseGraph<V, E> implements
		PrerequesiteOrderSetGraph<V, E> {

	private static final long					serialVersionUID	= 1L;
	private final TransitiveClosureGraph<V, E>	transitiveClosureGraph;
	private transient final Logger				log;

	@Inject
	JungPrerequesiteGraph(TransitiveClosureGraph<V, E> tcg, Logger log) {
		this.log = log;
		this.transitiveClosureGraph = tcg;
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public boolean addEdge(E edge, Pair<? extends V> endpoints,
			EdgeType edgeType) {
		if (endpoints.getFirst().equals(endpoints.getSecond())) {
			return false;
		} else if (this.transitiveClosureGraph.findEdge(endpoints.getFirst(),
				endpoints.getSecond()) == null) {
			// this is already an inferred relation...
			if (this.transitiveClosureGraph.addEdge(edge, endpoints, edgeType)) {
				// Now it is also cycle free
				if (super.addEdge(edge, endpoints, edgeType)) {
					synchronized (this) {
						removeInferredEdges(endpoints.getFirst(),
								endpoints.getSecond(), true);
						removeInferredEdges(endpoints.getFirst(),
								endpoints.getSecond(), false);
					}
					// finally if the adding succeeded fire event changed
					this.log.log(
							Level.INFO,
							"Added Edge {0} -> {1}",
							new Object[] { endpoints.getFirst().getName(), endpoints
									.getSecond().getName() });
					return true;
				} else {
					return false;
				}
			} else {
				// return false if transitive closure graph could not be
				// updated.
				this.log.log(
						Level.INFO,
						"Cycle detected on {0} -> {1}.",
						new Object[] { endpoints.getFirst().getName(), endpoints
								.getSecond().getName() });
				return false;
			}
		} else {
			// All other cases are "false".
			this.log.log(Level.INFO, "Edge {0} -> {1} is already infered!",
					new Object[] { endpoints.getFirst().getName(), endpoints
							.getSecond().getName() });
			return false;
		}
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public boolean addVertex(V vertex) {
		this.transitiveClosureGraph.addVertex(vertex);
		boolean addVertex = super.addVertex(vertex);
		this.log.info("Added Vertex " + vertex);
		return addVertex;
	};

	/**
	 * 
	 * @return an unmodifiable view to the closure of the prerequisite graph.
	 */
	@Override
	public ObservableGraph<V, E> getTransitiveClosureGraph() {
		return new ObservableGraph<V, E>(this.transitiveClosureGraph);
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public boolean removeEdge(E edge) {
		Pair<V> enpoints = getEndpoints(edge);
		boolean removeEdge = super.removeEdge(edge);
		E edge2 = this.transitiveClosureGraph.findEdge(enpoints.getFirst(),
				enpoints.getSecond());
		this.transitiveClosureGraph.removeEdge(edge2);
		return removeEdge;
	}

	// Do a BFS search to remove already inferred edges
	private void removeInferredEdges(V source, V target, boolean incoming) {
		List<V> currentVertices = new ArrayList<V>();
		Set<V> visitedVertices = new HashSet<V>();
		Set<E> visitedEdges = new HashSet<E>();
		Set<V> acceptedVertices = new HashSet<V>();
		Set<E> edgesToBeRemoved = new HashSet<E>();

		// Copy, mark, and add all the root nodes to the new subgraph
		if (incoming) {
			visitedVertices.add(source);
			acceptedVertices.add(source);
			currentVertices.add(source);
		} else {
			visitedVertices.add(target);
			acceptedVertices.add(target);
			currentVertices.add(target);
		}

		ArrayList<V> newVertices = null;
		int currentDepth = 0;
		while (currentDepth < getVertexCount()) {
			newVertices = new ArrayList<V>();
			for (V currentVertex : currentVertices) {

				Collection<E> edges = null;
				if (incoming) {
					edges = getInEdges(currentVertex);
				} else {
					edges = getOutEdges(currentVertex);
				}

				for (E currentEdge : edges) {

					V currentNeighbor = getOpposite(currentVertex, currentEdge);
					if (!visitedEdges.contains(currentEdge)) {
						visitedEdges.add(currentEdge);
						if (!visitedVertices.contains(currentNeighbor)) {
							visitedVertices.add(currentNeighbor);
							E edge = null;
							if (incoming) {
								edge = findEdge(currentNeighbor, target);
							} else {
								edge = findEdge(source, currentNeighbor);
							}
							if (edge != null) {
								edgesToBeRemoved.add(edge);
							}
							acceptedVertices.add(currentNeighbor);
							newVertices.add(currentNeighbor);
						}
					}
				}
			}
			currentVertices = newVertices;
			currentDepth++;
		}

		for (E e : edgesToBeRemoved) {
			log.log(Level.INFO, "Inferred edge {0} removed.", getEndpoints(e));
			super.removeEdge(e); // this is a special case removal.
			// Do only remove edges which are in the minimal transitive closure
			// representation only. This does not affect the full
			// transitive closure graph.
		}

	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public boolean removeVertex(V vertex) {
		boolean removeVertex = super.removeVertex(vertex);
		this.transitiveClosureGraph.removeVertex(vertex);
		return removeVertex;
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public boolean contains(V vertex) {
		return containsVertex(vertex);
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public int size() {
		return getVertexCount();
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public boolean containsPrerequesite(PrerequesiteRelation prerequisite) {
		@SuppressWarnings("unchecked") V ancestor = (V) prerequisite
				.getAncestor();
		@SuppressWarnings("unchecked") V descendant = (V) prerequisite
				.getDescendant();
		return findEdge(ancestor, descendant) != null;
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public ImmutableSet<V> getPrerequisites(V vertex) {
		return ImmutableSet.copyOf(getPredecessors(vertex));
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public ImmutableSet<V> getDescendants(V vertex) {
		Collection<V> successors = getSuccessors(vertex);
		if (successors == null) {
			return ImmutableSet.of();
		} else {
			return ImmutableSet.copyOf(successors);
		}
	}

	/**
	 * {@inheritDoc}
	 */
	@SuppressWarnings("unchecked")
	@Override
	public ImmutableSet<PrerequesiteRelation> getPrerequisites() {
		return (ImmutableSet<PrerequesiteRelation>) ImmutableSet.copyOf(this
				.getEdges());
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public ImmutableSet<V> getCbKSTVertices() {
		return ImmutableSet.copyOf(getVertices());
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public boolean addPrerequesite(PrerequesiteRelation prerequisite) {
		@SuppressWarnings("unchecked") E prerequisite2 = (E) prerequisite;
		@SuppressWarnings("unchecked") V ancestor = (V) prerequisite
				.getAncestor();
		@SuppressWarnings("unchecked") V descendant = (V) prerequisite
				.getDescendant();
		return this.addEdge(prerequisite2, ancestor, descendant);
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public boolean removePrerequesite(PrerequesiteRelation prerequisite) {
		@SuppressWarnings("unchecked") V ancestor = (V) prerequisite
				.getAncestor();
		@SuppressWarnings("unchecked") V descendant = (V) prerequisite
				.getDescendant();
		return this.removeEdge(findEdge(ancestor, descendant));
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public void addAll(ImmutablePrerequesiteOrderSet<V> set) {
		ImmutableSet<V> vertices = set.getCbKSTVertices();
		for (V v : vertices) {
			this.addVertex(v);
		}

		ImmutableSet<PrerequesiteRelation> s = set.getPrerequisites();
		for (PrerequesiteRelation prerequesiteRelation : s) {
			this.addPrerequesite(prerequesiteRelation);
		}
	}

	@Override
	public void addGraphEventListener(GraphEventListener<V, E> l) {

	}

	@Override
	public void removeGraphEventListener(GraphEventListener<V, E> l) {

	}

	@Override
	public boolean add(V vertex) {
		return this.addVertex(vertex);
	}

	@Override
	public V find(String id) {
		// TODO Auto-generated method stub
		Collection<V> vertices = super.getVertices();
		for (V vertex : vertices) {
			if (vertex.getId().equals(id)) {
				return vertex;
			}
		}
		return null;
	}

}
